package com.hr.牛客网剑指offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhz
 * @date 2020/08/21
 **/
public class JZ4_重建二叉树 {
    Map<Integer,Integer> dic=new HashMap<>();
    int[] po;
    /**
     *
     * @param pre 前序遍历数组
     * @param in 中序遍历数组
     * @return
     */
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {

        po=pre;
        for (int i = 0; i < in.length; i++) {
            dic.put(in[i],i);//记录每一个叶子值所对应的数组下标
        }
        return recur(0,0,in.length-1);
    }

    private TreeNode recur(int pre_root, int in_left, int in_right) {
        if (in_left>in_right){
            return null;
        }
        TreeNode root = new TreeNode(po[pre_root]);

        int i = dic.get(po[pre_root]);
        root.left = recur(pre_root + 1, in_left, i - 1);
        root.right = recur(pre_root + i - in_left + 1, i + 1, in_right);
        return root;
    }
}
